//************************************************************
//    > File Name: maximum-subarray.cpp
//    > Author: davis
//    > Mail:  
//    > Created Time: 2017年03月21日 17:10:12
//***********************************************************
//lintcode #41
#include<bits/stdc++.h>
using namespace std;
int maxSubArray(vector<int> nums){
	int sum=0,mx=INT_MIN;
	for(int i=0;i<nums.size();++i){
		sum += nums[i];
		mx=max(sum,mx);
		sum=max(sum,0);
	}
	return mx;
}
int main(){
	vector<int> nums={
		-2,2,-3,4,-1,2,1,-5,3
	};
	int mx=maxSubArray(nums);
	cout<<mx<<endl;
}
